
/**
*	Universidad del Valle de Guatemala
*	Algoritmos y Estructuras de Datos
*	Hoja de Trabajo 3
*	Carlos Alvarez, 11004
*	Rafael Mendez, 11171
*       Rafael Berganza, 09135
*	Rodrigo Avelar, 11192
 *      Jose Angel Estrada, 11453
*	Sorts.java
*	Descripción: Esta clase tiene los ordenamientos
**/
public class Sorts{
    
    /**
     * insertionSort
     *      Ordenamiento mediante el algoritmo de insercion, tomado de los
     *      autores Lewis y Loftus
     * @param list objeto que implementa la interfaz comparable
     */
    public static void insertionSort (Comparable[] list)
   {
      for (int index = 1; index < list.length; index++)
      {
         Comparable key = list[index];
         int position = index;

         //  Shift larger values to the right
         while (position > 0 && key.compareTo(list[position-1]) < 0)
         {
            list[position] = list[position-1];
            position--;
         }
            
         list[position] = key;
      }
   }
   
    /**
     * bubbleSort
     * Ordenamiento mediante el algoritmo de bubble 
     * 
     * @param a objeto que implementa la interfaz comparable
     * @param n el numero de elementos del objeto a 
     */
    public static void bubbleSort(Comparable[] a, int n)
    // pre: 0 <= n <= data.length
    // post: values in data[0..n-1] in ascending order
    {
        int i, j;
        Comparable t=0;
        for(i = 0; i < n; i++){
            for(j = 1; j < (n-i); j++){
                if((a[j-1].compareTo(a[j])) > 0){
                    t = a[j-1];
                    a[j-1]=a[j];
                    a[j]=t;
                }
            }
        }
    }
    /**
     * mergesort
     *      Ordenamiento mediante de mezcla, tomado del 
     *      autor Sun Microsystems.
     * @param list: recibe un parametro tipo comparable.
     */
  public static void mergesort(Comparable[] list)
   {
       Comparable [ ] temp = new Comparable[ list.length ];
       mergeSort( list, temp, 0, list.length - 1 );
       
       
   }
  /**
   * mergesort
   *    Ordenamiento mediante de mezcla, tomado del 
   *      autor Sun Microsystems.
   * @param list un arreglo de tipo comparable.
   * @param temp arreglo donde se coloca el arreglo unido.
   * @param left El indice mas a la izquierda del sub arreglo.
   * @param right El indice mas a la derecha del sub arreglo.
   */
   private static void mergeSort( Comparable [ ] list, Comparable [ ] temp,
            int left, int right ) {
        if( left < right ) 
        {
            int center = ( left + right ) / 2;
            mergeSort( list, temp, left, center );
            mergeSort( list, temp, center + 1, right );
            merge( list, temp, left, center + 1, right );
        }
    }
   /**
    * Ordenamiento mediante de mezcla, tomado del 
    *      autor Sun Microsystems
    * @param list un arreglo de tipo comparable.
    * @param temp arreglo donde se coloca el arreglo unido.
    * @param leftPos El índice más a la izquierda del sub arreglo.
    * @param rightPos El índice del inicio de la segunda mitad.
    * @param rightEnd el índice más a la derecha de la subarreglo.
    */
   private static void merge( Comparable [ ] list, Comparable [ ] temp,
            int leftPos, int rightPos, int rightEnd ) {
        int leftEnd = rightPos - 1;
        int tmpPos = leftPos;
        int numElements = rightEnd - leftPos + 1;
        
        // Main loop
        while( leftPos <= leftEnd && rightPos <= rightEnd )
            if( list[ leftPos ].compareTo( list[ rightPos ] ) <= 0 )
                temp[ tmpPos++ ] = list[ leftPos++ ];
            else
                temp[ tmpPos++ ] = list[ rightPos++ ];
        
        while( leftPos <= leftEnd )    // Copy rest of first half
            temp[ tmpPos++ ] = list[ leftPos++ ];
        
        while( rightPos <= rightEnd )  // Copy rest of right half
            temp[ tmpPos++ ] = list[ rightPos++ ];
        
        // Copy tmpArray back
        for( int i = 0; i < numElements; i++, rightEnd-- )
            list[ rightEnd ] = temp[ rightEnd ];
    }
   /**
    * 
    * @param v objeto que implementa la interfaz comparable
    * @param be asgina el numero 0
    * @param t es la cantidad de elementos del objeto menos 1
    * @return 
    */
   public static int colocar(Comparable [] v, int b, int t)
    {
        int i;
        int pivote;
        Comparable valor_pivote;
        Comparable temp;

        pivote = b;
        valor_pivote = v[pivote];
        for (i=b+1; i<=t; i++){
            if (v[i].compareTo(valor_pivote) < 1){
                     pivote++;    
                    temp=v[i];
                    v[i]=v[pivote];
                    v[pivote]=temp;

            }
        }
        temp=v[b];
        v[b]=v[pivote];
        v[pivote]=temp;
        return pivote;
    } 
 
   /**
    * Quicksort
    * Ordenamiento mediante el algoritmo quick, tomado de Wikipedia
    * 
    * @param v objeto que implementa la interfaz comparable
    * @param b se asgina el numero 0
    * @param t es la cantidad de elementos del objeto menos 1
    */
     public static  void Quicksort(Comparable []v, int b, int t)
    {
         int pivote;
         if(b < t){
            pivote=colocar(v, b, t);
            Quicksort(v, b, pivote-1);
            Quicksort(v, pivote+1, t);
         }  
    }

}
           
    
    


